Tương truyền, Trò Xuân Phả bắt nguồn từ đời nhà Đinh, sau khi Đinh Bộ Lĩnh dẹp loạn 12 sứ quân và lên ngôi vua.[2][3]

Truyền thuyết địa phương kể lại rằng, vào thời Vua Đinh, đất nước có nạn giặc ngoại xâm, nhà Vua sai sứ giả đi khắp nơi cầu bách linh, bách tính và hiền tài cùng nhau đứng lên đánh giặc cứu nước. Khi sứ giả đi đến bờ sông Chu thì gặp giông tố phải trú lại trong Nghè Xuân Phả. Đến đêm, thần Thành hoàng làng Xuân Phả báo mộng về cách phá giặc, sứ giả vội về bẩm cáo lại với nhà Vua. Vua thấy kế hay nên làm theo và quả nhiên thắng trận. Để tỏ lòng biết ơn Thành hoàng làng Xuân Phả, nhà Vua đã phong tặng tước vương gọi là Đại Hải Long Vương. Nhà vua còn ban thưởng cho dân Xuân Phả năm điệu múa trò để hàng năm dâng lên Thành hoàng trong ngày hội làng. Có thể khẳng định rằng TXP là vũ điệu dân gian giành riêng cho Đại Hải Long Vương thành hoàng làng Xuân Phả.

Ngày nay, ở xã Thọ Tân, Triệu Sơn, Thanh Hóa còn đền thờ Vua Đinh Tiên Hoàng và những ghi chép về nguồn gốc hình thành Trò Xuân Phả [4] như sau:

Khi Đinh Bộ Lĩnh tiến hành dẹp loạn 12 sứ quân thống nhất đất nước Đại Cồ Việt có dẫn nghĩa quân đi dẹp sứ quân Ngô Xương Xí ở Bình Kiều - Ái Châu (Thanh Hóa ngày nay). Vua kéo quân đến đất Quan Thành thì dựng trại, đóng quân tại đây. Đinh Bộ Lĩnh cử sứ giả đi cầu Bách linh mong âm phù giúp ba quân đánh thắng trận. Sứ giả nhận mệnh đi đường thủy ngược dòng sông Sử (tức Sông Chu) lên đến đất Vụng Tậu thì trời vừa tối, sứ giả neo thuyền tại Vụng Tậu phía sau đền thờ vị thần: Đại Hải Long Vương, một vị thần linh thiêng nổi tiếng của huyện Lôi Dương (Thọ Xuân), là Thần Hoàng làng của làng Xuân Phả. Khi giang sơn thống nhất, các bộ tộc và các nước lân bang mang lễ vật triều cúng và ca vũ mừng nhà vua lên ngôi... Tưởng nhớ đến công lao người đã âm phù thắng trận, Vua Đinh đã cho đem toàn bộ cống phẩm và trò diễn đến đền thờ Đại Hải Long Vương mà không lưu lại ở kinh đô Hoa Lư. Vua lại giao cho bà hoàng hậu Dương Thị Nguyệt quê ở Hà Nam chủ trì việc này. Bà xuất thân vốn là một ca vũ cung đình, đã tiếp thu các điệu múa của các nước lân bang và huấn luyện thành đội múa hàng, hàng năm cứ đến ngày 10-2 âm lịch, bà trực tiếp hướng dẫn đội múa đến biểu diễn tại đền thờ thần Đại Hải Long Vương. Về sau dân làng Xuân Phả xin bà truyền bá điệu múa ấy cho dân làng tự tập, tự diễn, từ đấy trở đi điệu múa cũng có tên là múa Xuân Phả (hay còn gọi là Ngũ quốc lân bang đồ cống tiến) và được các thế hệ người dân lưu truyền đến ngày nay, trở thành một sinh hoạt văn hóa độc đáo ở Xứ Thanh.

Từ lễ hội ăn mừng chiến thắng, các nước lân cận đem lễ vật đến tiến cống, chúc mừng nhà vua đất Việt, với cả các điệu múa như Ai Lao (nước Lào), Chiêm Thành (dân tộc Chăm ở phía Nam); Ngô Quốc (bộ tộc của đảo Hải Nam Trung Quốc); Lục Hồn Nhung (bộ tộc Lục Hồn ở Mông Cổ); Hoa Lang (một bộ tộc Cao Ly ở Triều Tiên). Ngay sau đó, để đền đáp công ơn, nhà vua đã ban 5 điệu múa trên cho nhân dân làng Xuân Phả với tên gọi “Ngũ quốc lân bang đồ tiến công”.[5]